% Ejercicio "Longitud de listas en PROLOG"
\subsection*{\fbox{\theejercicio} - Longitud de listas en PROLOG}

La siguiente gram\'atica corresponde a la fase sint\'actica del an\'alisis de algunas listas v\'alidas en PROLOG:

\begin{center}
\begin{tabular}{|lcl|} \hline
                &               &                             \\
{\em Lista}     & $\rightarrow$ & [ ]                         \\
{\em Lista}     & $\rightarrow$ & [ {\em T\'ermino} ]         \\
{\em T\'ermino} & $\rightarrow$ & {\em T\'ermino , T\'ermino} \\
{\em T\'ermino} & $\rightarrow$ & {\bf IDENTIFICADOR}         \\
{\em T\'ermino} & $\rightarrow$ & {\em Lista}                 \\
         &               &                                    \\ \hline
\end{tabular}
\end{center}

En donde los {\bf IDENTIFICADORES} son secuencias de caracteres alfanum\'ericos que comienzan por una letra min\'uscula.

\smallskip

Se define como longitud de una lista al n\'umero de t\'erminos que la componen. Se define como extensi\'on de una lista, a la longitud m\'axima de cualquier sublista contenida en ella.

\smallskip

Ejemplo: La lista:

\begin{center}\verb@[ [a1,a2], a3, [a4,[a5,a6],[a7],a8] ]@\end{center}

tiene una longitud de 3 y una extensi\'on de 4.

\begin{enumerate}[1)]
\item Construir mediante LEX y YACC un programa capaz de procesar una lista y averiguar su longitud
\item Construir mediante LEX y YACC un programa capaz de procesar una lista y averiguar su extensi\'on.
\end{enumerate}

NOTA: Para la resoluci\'on de este ejercicio deben utilizarse las variables y atributos propios de LEX y YACC, no siendo v\'alida la definici\'on de ninguna otra variable auxiliar.

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Ambos apartados pueden resolverse conjuntamente mediante los siguientes programas:

\underline{ESPECIFICACI\'ON LEX}:

\begin{verbatim}
%%
[a-z][a-zA-Z0-9]*     { return ID; }
\,                    { return `,'; }
\[                    { return `['; }
\]                    { return `]'; }
[\ \t\n]+             { ; }
.                     { fprintf(yyout,"Error lexicografico \n"); }
%%
\end{verbatim}

\underline{ESPECIFICACI\'ON YACC}:

\begin{verbatim}
%{
typedef struct { int l,ext; } YYSTYPE;
#define max(x,y) (x>y?x:y)
%}

%token ID
%left `,'

%%
axioma: lista                  { printf("La longitud es %d \n",$1.l);
                                 printf("La extension es %d \n",$1.ext);
                               }
      ;

lista: `[' `]'                 { $$.l = 0; $$.ext = 0; }
     | `[' termino `]'         { $$.l = $2.l; $$.ext = max($2.l,$2.ext); }
     ;

termino: termino `,' termino   { $$.l = $1.l+1;$$.ext = max($1.ext,$3.ext)
       | ID                    { $$.l = 1; $$.ext = 1; }
       | lista                 { $$.l = 1; $$.ext = max($1.l,$1.ext);
       ;
%%
#include "lexyy.c"
#include "..\mainyacc.c"
\end{verbatim}